package cn.ac.cintcm.prespring.tree;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;

import cn.ac.cintcm.prespring.util.IndexFile;

public class Ladder {
    private IndexFile index;
    
    public Ladder(IndexFile index) {
        this.index = index;
    }
    
    public VisitMemory getLadder(String idStr) {
        int id = Integer.parseInt(idStr);
        
        VisitMemory vm = new VisitMemory(id);
        findLadder(index, id, vm);
        return vm;
    }
    
    /**
     * ??????????????????????
     * @param id ???????
     * @param ip ?????????Χ?????????
     * @param vp ???????
     */
    public void findLadder(IndexFile ip, int id,  Visit vp) {
        List<Integer> list = ip.getIdListIndex().get(id);
        vp.setRoot(id);
        iteratorMinusSearch(id, ip, vp);
        iteratorPlusSearch(id, ip, vp);
        vp.visit(0, list.size(), 0, id);
    }
    
    /**
     * ???????????????
     * @param id ???????
     * @param ip ?????????Χ?????????
     * @param vp ???????
     */
    private void iteratorMinusSearch(int id, IndexFile ip, Visit vp) {
        List<Integer> list = ip.getIdListIndex().get(id);
        if (list != null) {
            int countIndex = list.size() - 1;
            if (countIndex > 0) {
                //??????????ζ?????е?????ζ??????з???
                List<Integer> intersection = ip.getSizeListIndex().get(countIndex);
                if (intersection != null) {
                    //?????????ζ???￡???????????????ζ?????????????????????hash??
                    for (int i = 0; i < list.size(); i++) {
                        //??b???ζ????????????????
                        Integer[] dest = new Integer[countIndex];
                        Integer[] src = list.toArray(new Integer[0]);
                        Integer exclusiveHerb = src[i];
                        if (i > 0) {
                            System.arraycopy(src, 0, dest, 0, i);
                        }
                        System.arraycopy(src, i+1, dest, i, list.size()-i-1);
                        List<Integer> subList = java.util.Arrays.asList(dest);
                        //?????ζ???????????????????ζ?????Ｏ????????????
                        Integer parent = -1;
                        for (Integer p : intersection) {
                            //?б?????????ζ????????????????????u??????????
                            List<Integer> herbs = ip.getIdListIndex().get(p);
                            if (herbs != null 
                                    && herbs.containsAll(subList)) {
                                //?????????????????????????????ζ????????t????
                                //??????????????
                                if (parent < p) {
                                    parent = p;
                                }
                                //???????????????}??д???
                                vp.visit(id, countIndex, exclusiveHerb, p);
                            }
                        } //end for (Integer p: intersection)
                        //??????????ζ?????c??????????ζ?????
                        if (parent != -1) {
                            iteratorMinusSearch(parent, ip, vp);
                        }
                    }//end for (int i=0;...
                }
            }//end if (countIndex > 1)
        }//end if (list != null)
    }
    
    /**
     * ??????????????????
     * @param id ???????
     * @param ip ?????????Χ?????????
     * @param vp ???????
     */
    private void iteratorPlusSearch(int id, IndexFile ip, Visit vp) {
        int parent = id;
        List<Integer> list = ip.getIdListIndex().get(id);
        if (list != null) {
            int countIndex = list.size() + 1;
            if (ip.getSizeListIndex().containsKey(countIndex)) {
                //??????ж??ζ?????е?????ζ??????з???
                List<Integer> intersection = ip.getSizeListIndex().get(countIndex);
                //?????????????????????????
                HashMap<Integer, Integer> rsMap = new HashMap<Integer, Integer>();            
                if (intersection != null) {
                    List<Integer> compare = null;
                    for (Integer p : intersection) {
                        //?б?????????ζ????????????????????u??????????
                        List<Integer> herbs = ip.getIdListIndex().get(p);
                        if (herbs != null ) {
                            compare = new ArrayList<Integer>(herbs);
                            compare.removeAll(list);
                            if (compare.size() == 1) {
                                int exclusiveHerb = compare.toArray(new Integer[0])[0];
                                Integer visited = rsMap.get(exclusiveHerb);
                                //??????id????е??
                                if (visited == null || visited < p) {
                                    rsMap.put(exclusiveHerb, p);
                                }
                            }
                        }
                    } //end for (Integer p: intersection)
                    if (rsMap.size() > 0) {
                        //??????????ζ?????c??????????ζ?????
                        for (Integer h : rsMap.keySet()) {
                            vp.visit(parent, countIndex, h, rsMap.get(h));
                            iteratorPlusSearch(rsMap.get(h), ip, vp);
                        }
                    }
                }
            }//end if hcp.containsKey(countIndex)
        }//end if (list != null)
    }
}
